#include <iostream>
#include <vector>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;

// https://leetcode.cn/problems/maximum-candies-you-can-get-from-boxes/?envType=daily-question&envId=2025-06-03
// 1298. 你能从盒子里获得的最大糖果数

class Solution1
{
public:
    int maxCandies(vector<int> &status, vector<int> &candies, vector<vector<int>> &keys, vector<vector<int>> &containedBoxes, vector<int> &initialBoxes)
    {
        int ans = 0;
        if (initialBoxes.empty())
        {
            return ans;
        }
        // 获取初始糖果和初始钥匙
        unordered_set<int> keySet;
        deque<int> boxSet;
        for (int i = 0; i < initialBoxes.size(); i++)
        {
            int curBox = initialBoxes[i];
            if (status[curBox] == 1)
            {
                ans += candies[curBox];
                // 钥匙
                int keyCount = keys[curBox].size();
                keySet.insert(keys[curBox].begin(), keys[curBox].begin() + keyCount);
                // 箱子集合
                int boxCount = containedBoxes[curBox].size();
                boxSet.insert(boxSet.end(), containedBoxes[curBox].begin(), containedBoxes[curBox].begin() + boxCount);
            }else{
                boxSet.push_back(curBox);
            }
        }

        while (!boxSet.empty())
        {
            int curBox = boxSet[0];
            if (keySet.find(curBox) == keySet.end() || status[curBox] == 0)
            {
                boxSet.pop_front();
                boxSet.push_back(curBox);
                continue;
            }
            auto it = keySet.find(curBox);
            keySet.erase(it);
            ans += candies[curBox];
            int keyCount = keys[curBox].size();
            keySet.insert(keys[curBox].begin(), keys[curBox].begin() + keyCount);
            // 箱子集合
            int boxCount = containedBoxes[curBox].size();
            boxSet.insert(boxSet.end(), containedBoxes[curBox].begin(), containedBoxes[curBox].begin() + boxCount);
            boxSet.pop_front();
        }
        return ans;
    }
};

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, 
                   vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {

        int n = status.size();
        vector<bool> hasBox(n, false), used(n, false);
        queue<int> q;
        unordered_set<int> keySet;
        for (int box : initialBoxes) {
            hasBox[box] = true;
            if (status[box] == 1) {
                q.push(box);
                used[box] = true;
            }
        }

        int ans = 0;
        while (!q.empty()) {
            int box = q.front();
            q.pop();
            ans += candies[box];

            // 获得钥匙
            for (int key : keys[box]) {
                if (status[key] == 0) {
                    status[key] = 1;
                    if (hasBox[key] && !used[key]) {
                        q.push(key);
                        used[key] = true;
                    }
                }
            }

            // 获得新箱子
            for (int newBox : containedBoxes[box]) {
                hasBox[newBox] = true;
                if (status[newBox] == 1 && !used[newBox]) {
                    q.push(newBox);
                    used[newBox] = true;
                }
            }
        }
        return ans;
    }
};

int main()
{
    return 0;
}